

// 结点类
class Node {
    constructor(data) {
        this.data = data;
        this.right = null;
        this.left = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    //查找结点
    search(data) {
        let targetNode = this.root;
        while (targetNode!=null && targetNode.data != data) {
            if (data > targetNode.data) {
                targetNode = targetNode.right;
            } else {
                targetNode = targetNode.left;
            }
        }
        if(targetNode == null){
            console.log("未找到结点：" + data);
        } else {
            console.log("已找到结点：" + data);
        }
        return targetNode;
    }

    //中序遍历
    static inOrderTraversal( node){
        if(node == null){
            return;
        }
        BinarySearchTree.inOrderTraversal(node.left);
        console.log(node.data + " ");
        BinarySearchTree.inOrderTraversal(node.right);
    }

    //插入结点
    insert(data) {
        let node = new Node(data);
        if(this.root == null){
            this.root = node;
            return true;
        }
        let targetNode  = this.root;
        while (targetNode != null) {
            if( data == targetNode.data){
                console.log("二叉查找树中已有重复的结点：" + data);
                return false;
            }else if (data > targetNode.data) {
                if(targetNode.right == null){
                    targetNode.right = node;
                    return true;
                }
                targetNode = targetNode.right;
            }else {
                if(targetNode.left == null){
                    targetNode.left = node;
                    return true;
                }
                targetNode = targetNode.left;
            }
        }
        return true;
    }

    //删除结点
    delete(data) {
        let targetNode = this.root;
        let parentNode = new Node(data);
        //判断待删除结点是否存在
        while (targetNode.data != data) {
            parentNode = targetNode;
            if (data > targetNode.data) {
                targetNode = targetNode.right;
            } else {
                targetNode = targetNode.left;
            }
            if (targetNode == null) {
                // 没有找到待删除结点
                return false;
            }
        }
        // 待删除结点没有子节点
        if (targetNode.right==null && targetNode.left==null) {
            if (targetNode == this.root) {
                //待删除结点是根结点
                root = null;
            } else {
                if (parentNode.right == targetNode) {
                    parentNode.right = null;
                } else {
                    parentNode.left = null;
                }
            }
        }
        //待删除结点有一个子结点（右）
        else if(targetNode.left == null) {
            if(targetNode == this.root) {
                root = targetNode.right;
            } else if(parentNode.right == targetNode) {
                parentNode.right = targetNode.right;
            } else {
                parentNode.left = targetNode.right;
            }
        }
        //待删除结点有一个子结点（左）
        else if(targetNode.right == null) {
            if(targetNode == this.root) {
                root = targetNode.left;
            } else if(parentNode.right == targetNode) {
                parentNode.right = targetNode.left;
            } else {
                parentNode.left = targetNode.left;
            }
        }
        //待删除结点有两个子结点
        else {
            //待删除结点的后继结点的父结点
            let successParentNode = targetNode;
            //待删除结点的后继结点
            let successNode = targetNode.right;
            while(successNode.left != null)
            {
                successParentNode = successNode;
                successNode = successNode.left;
            }
            //把后继结点复制到待删除结点位置
            targetNode.data = successNode.data;
            //删除后继结点
            if(successParentNode.right == successNode) {
                successParentNode.right = successNode.right;
            } else {
                successParentNode.left = successNode.right;
            }
        }
        return true;
    } 
}
let tree = new BinarySearchTree();
let input= [6,3,8,2,5,7,9,1,4];
for(let i=0; i<input.length; i++) {
    tree.insert(input[i]);
}
BinarySearchTree.inOrderTraversal(tree.root);
tree.search(3);
tree.delete(3);
tree.search(3);
tree.delete(6);
BinarySearchTree.inOrderTraversal(tree.root);